/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-distinct-islands-ii
   @Language: C++
   @Datetime: 19-06-14 14:24
   */

class Solution {
	vector<pair<int,int> > bfs(vector<vector<int> > &grid, int r, int c){
		int rows=grid.size(), cols=grid[0].size(), row=r, col=c;
		int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
		queue<pair<int,int> > q;
		vector<pair<int,int> > island;
		for(q.push({r,c}); q.size(); q.pop()){
			r=q.front().first, c=q.front().second;
			if(r<0 || r>=rows || c<0 || c>=cols) continue;
			if(grid[r][c]==0) continue;
			grid[r][c]=0;
			island.push_back({r-row,c-col});
			for(int i=4; i--; q.push({r+dir[i][0],c+dir[i][1]}));
		}
		return island;
	}
	static bool pairless(const pair<int,int> &a, const pair<int,int> &b){
		if(a.first==b.first) return a.second<b.second;
		else return a.first<b.first;
	}
	bool contain(unordered_set<string> &islands, vector<pair<int,int> > &island){
		int dir[][4]={{1,0,0,1},{0,-1,1,0},{-1,0,0,-1},{0,1,-1,0},{-1,0,0,1},{1,0,0,-1}};
		vector<string> strs;
		for(int d=0; d<6; ++d){
			vector<pair<int,int> > vp;
			for(const auto &p:island){
				const int &i=p.first, &j=p.second;
				vp.push_back({i*dir[d][0]+j*dir[d][1],i*dir[d][2]+j*dir[d][3]});
			}
			sort(vp.begin(),vp.end(),pairless);
			string str;
			int row=vp.begin()->first, col=vp.begin()->second;
			for(const auto &p:vp)
				str.append(to_string(p.first-row)+" "+to_string(p.second-col)+" ");
			if(islands.count(str)) return true;
			else strs.push_back(str);
		}
		for(const auto &str:strs)
			islands.insert(str);
		return false;
	}
public:
	/**
	 * @param grid: the 2D grid
	 * @return: the number of distinct islands
	 */
	int numDistinctIslands2(vector<vector<int> > &grid) {
		// write your code here
		unordered_set<string> islands;
		int cnt=0;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j]){
					auto island=bfs(grid,i,j);
					if(!contain(islands,island)) ++cnt;
				}
		return cnt;
	}
};
